package demo1;

import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-07-25
 * Time: 11:02
 */



/**
 * 单链表实现队列
 * 无论从头入队还是从尾入队, 要满足队列先进先出, 总会存在出对或入队是时间复杂度为 O(n)
 */
public class MyQueue {

    // 内部类单链表
    public static class ListNode {
        public int val;
        public ListNode next;

        // 内部类单链表构造方法
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head; // 头结点

    public ListNode tail; // 尾节点

    private int usedSize;

    /**
     * 入队列方法
     * 想要实现一个入队列和出队列时间复杂度都是 O(1) 的操作, 考虑首次头插入队, 后续尾插入队
     * @param val 入队列元素
     */
    public void offer(int val) {

        ListNode node = new ListNode(val);

        if(head == null) {
            // 首次头插
            head = node;
            tail = node;
        }else {
            // 后续尾插
            tail.next = node;
            tail = tail.next;
        }

        usedSize++; // 记录当前队列中有几个元素
    }

    /**
     * 出队列 -- 满足先进先出
     */
    public int pop() {

        // 队列为空
        if(empty()) {
            throw new EmptyException("当前队列为空, 无法继续弹出队列元素");
        }

        // 记录头结点值
        int target = head.val;

        // 删除头结点, 指向下一个位置
        head = head.next;

        // TODO : 如果只有一个节点的时候, head 和 tail 都指向这个节
        //        点, 如果这个节点删除, 还需要将 tali 置空, 否则 tail
        //        依然指向这个节点

        // 判断删除的是否为队列中最后一个节点
        if(head == null) {
            tail = null;
        }

        // 更新元素个数
        usedSize--;

        // 返回头结点的值
        return target;
    }

    public boolean empty() {
        return usedSize == 0 || head == null;
    }

    public int getUsedSize() {
        return usedSize;
    }

    public void setUsedSize(int usedSize) {
        this.usedSize = usedSize;
    }
}
